package com.coder.algorithm.offer_2;

import java.util.Arrays;

/**
 * 数组中重复的数字
 *
 * @author yuhushuan
 * @date 2020/5/24 01:37
 */
public class _03_1_DuplicationInArray {
    public static void main(String[] args) {
        int[] data;

        // 长度为 n 的数组里包含一个或多个重复的数字
        data = new int[]{2, 3, 1, 0, 2, 5, 3};
        print(data, data.length);

        // 数组中不包含重复的数组
        data = new int[]{6, 3, 1, 0, 2, 5, 4};
        print(data, data.length);

        // 无效输入测试用例（输入空指针；长度为 n 的数组中包含 0～n-1之外的数字）。
        print(null, 2);

        data = new int[]{6, 3, 1, 10, 2, 5, 4};
        print(data, data.length);
    }


    private static void print(int[] data, int length) {
        System.out.println(String.format("%s 中存在重复数字 %b", Arrays.toString(data), duplicate(data, length)));
    }


    /**
     * 题目一：找出数组中重复的数字
     * 在一个长度为 n 的数组里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，
     * 但不知道有几个数字重复了，也不知道每个数字重复了几次。
     * 请找出数组中任意一个重复的数字。例如，如果输入长度为 7 的数组
     * {2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或者3。
     *
     * @param numbers
     * @param length
     * @return
     */
    private static boolean duplicate(int[] numbers, int length) {
        if (null == numbers || length <= 0) {
            return false;
        }
        for (int i = 0; i < length; i++) {
            if (numbers[i] < 0 || numbers[i] > length - 1) {
                return false;
            }
        }
        for (int i = 0; i < length; i++) {
            while (numbers[i] != i) {
                if (numbers[i] == numbers[numbers[i]]) {
                    return true;
                }
                // swap numbers[i] and numbers[numbers[i]]
                int temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        return false;
    }
}
